Parallel data processing systems, or parallel processors, are widely utilized for computing applications which require that a substantially large amount of data be processed in a relatively small duration of time. Examples of such applications are real-time applications such as those required for image reception and recognition systems, seismic systems, and control systems adapted for controlling a device in response to a plurality of sensor input signals. Other applications include mathematical and physical science research, meteorology, and artificial intelligence systems.
A particular problem associated with known parallel processing systems is the complexity of the required interconnection of discrete processing elements and the interconnection of the individual processing elements with a central controlling processing element. A desirable goal in the design of such processors is the optimization of this interprocessor connectivity in that the nature of the connectivity typically affects the overall processing speed, efficiency, and ease of use of the system,
Related to this problem of connectivity optimization are constraints imposed by the expense and technical complexity of achieving the most optimal connectivity between the system processing elements.
In accordance with the invention there is disclosed a method for use in a parallel data processing system whereby individual processing elements or cells of an array of processing elements determine their position within the array, In an illustrative embodiment of the invention a parallel data processing system is comprised of at least a two dimensional array of data processing cells, each of the cells comprising a plurality of input and output communication signal lines for electrically coupling to at least all immediately neighboring cells. The method includes the following steps.
For at least one cell disposed at a predetermined position along a boundary of the array the cell has at least two cell input communication signal lines coupled to a predetermined logic state. A step initiates an input signal line logic state determination processing state within all of the cells of the array and a further step detects by the at least one cell at the predetermined position the predetermined logic state. For the cell so detecting the predetermined logic state the method includes a step of determining from the detected predetermined logic state that the cell is located at the predetermined position within the array.
For the cell so determining its position at the predetermined position within the array the method includes a step of communicating an identification of the predetermined position to at least one other neighboring cell whereby the neighboring cell so communicated to is enabled to determine its position within the array relative to the predetermined position.
The invention also teaches a method of verifying the operational integrity of an array of data processing cells by transmitting a position of at least one of the cells to a control data processor. The control data processor compares the transmitted position to a known position. If the two positions are not in agreement the control data processor determines that at least one cell of the array is inoperable to determine its position within the array and/or to communicate position information with a neighboring cell.